题解 P4643@洛谷 【[国家集训队]阿狸和桃子的游戏】

题意简述

我们有一个 $n$ 点 $m$ 边的无向图，有点权和边权。现在两个人将它按照自己的最优方案每次取一个点，分为两部分，求出此时他们的分差。

方法分析

边权不好处理，我们想到将它与点权合并。最容易想到的方法就是两个端点各加一半边权，这个方法也是正确的，正确性将在下方证明。

因为每个人都会按照自己的当前最优策略取，所以将整个权值排序后，编号为奇数的是一个人取的，偶数的是另一个人取的，我们只需要按照奇偶数分别算出总权值即可。

正确性证明

这里主要证明上面说的将边权与点权合并的正确性。

对于一条边 $e(u,v,w)$，设两端点的初始权值为 $a_u,a_v$，我们这里将两端点的权值改为了 $a_u+\frac{w}{2},a_v+\frac{w}{2}$。

情况一：$u,v$ 被同一个人取到。

此时，这个人的总权值为 $a_u+a_v+2\times\frac{w}{2}=a_u+a_v+w$，符合题意。

情况二：$u,v$ 被两人分别取到。

不妨设 $u$ 被第一个人取到。

此时，第一个人权值为 $a_u+\frac{w}{2}$，第二个人权值为 $a_v+\frac{w}{2}$。最后要将答案相减，得到 $a_u-a_v$，符合题意。

综上所述，这种方法正确。

代码与备注

在这份代码中，我们排序后按照从小到大顺序循环取值。由于题面保证 $n$ 为偶数，因此这个方法也没有问题。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;

int n, m; 
double a[N], s[2];

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++) scanf("%lf", &a[i]);
	for(int i=1;i<=m;i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		a[u] += w / 2.0;
		a[v] += w / 2.0; 
	}
	sort(a+1, a+1+n);
	for(int i=1;i<=n;i++) s[i&1] += a[i];
	printf("%.0lf\n", s[0]-s[1]);
	return 0;
}